A Power Law in Logarithm's Clothing: On the Scalability of Graph-Based Vector Search
图向量搜索的可扩展性：披着对数外衣的幂律
🧭 向量检索 · 图索引扩展性
University of Toronto
实测发现图向量搜索成本在数据规模小于内在维度时呈次线性幂律增长，之后才转入多对数增长，并给出统一理论模型
📌 工作参考价值（4 点）
- 容量规划：若数据规模 N 未达到由内在维度决定的临界点，搜索延迟/算力按 N^c（0<c<1）增长而非多对数；电商/推荐团队做向量库扩容预算时不能假设对数级成本，可用论文模型估计 c 和临界规模。
- 内在维度监控：数据集内在维度随规模增大而升高，导致查询邻域更密集；可在 embedding 上线前/后持续测量 intrinsic dimensionality，预测搜索成本拐点。
- 索引调参：论文提供预测不同 recall target 和索引配置下 power-law 指数的模型，可用来在 M、efSearch、efConstruction 等参数间做 cost-recall 权衡，适合高召回场景（广告召回、相关商品召回）提前规划。
- 评估方法借鉴：做 ANN 基准应跨多个数量级规模测试，而不是只在单点规模测量成本。